package main

func main() {

	//strsArray := []string{"a", "b", "c"}
	//str := "sssssss"

	//测试用例
	num1 := []int{1, 2, 3, 0, 0, 0} //后面的3个0是填充num2的长度
	num2 := []int{2, 5, 6}
	m := 3
	n := 3

	//打印测试用例返回结果
	merge(num1, m, num2, n)
	for _, v := range num1 {
		println(v)
	}
	//println(resp)

}

//倒序双指针
func merge(nums1 []int, m int, nums2 []int, n int) {
	if m == 0 { //边界条件
		for i := 0; i < m+n; i++ {
			nums1[i] = nums2[i]
		}
		return
	}
	if n == 0 { //边界条件
		return
	}
	//双指针的初始值
	ptr1, ptr2 := m-1, n-1
	//从nums1数组的末尾，由大至小填数。ptr3是nums1的末尾
	ptr3 := m + n - 1
	ptr1Flag := true //如果ptr1是负数，该flag就为false
	for ptr3 >= 0 {
		if nums1[ptr1] >= nums2[ptr2] && ptr1Flag { //移动相对大的值到末尾
			nums1[ptr3] = nums1[ptr1]
			ptr1--
			if ptr1 < 0 {
				ptr1 = 0
				ptr1Flag = false
			}
		} else {
			nums1[ptr3] = nums2[ptr2]
			ptr2--
			if ptr2 < 0 {
				break
			}
		}
		ptr3-- //末尾指针减少1
	}
}

//上面是我自己的题解，思想和官方答案一致，但是多了很多没必要的边界检验条件。
//下面是官方题解。非常优雅(但是时空复杂度和我的一致，思想也一致)
func mergeOfficial(nums1 []int, m int, nums2 []int, n int) {
	for p1, p2, tail := m-1, n-1, m+n-1; p1 >= 0 || p2 >= 0; tail-- {
		var cur int
		if p1 == -1 {
			cur = nums2[p2]
			p2--
		} else if p2 == -1 {
			cur = nums1[p1]
			p1--
		} else if nums1[p1] > nums2[p2] {
			cur = nums1[p1]
			p1--
		} else {
			cur = nums2[p2]
			p2--
		}
		nums1[tail] = cur
	}
}
